﻿#include <iostream>
#include <vector>
#include <unordered_map>
#include <queue>
#include <limits>
#include <string>
#include <tuple>

struct Edge {
    std::string to;
    int weight;
};

// 使用优先队列的比较函数
struct Compare {
    bool operator()(const std::pair<std::string, int>& a, const std::pair<std::string, int>& b) {
        return a.second > b.second; // 按距离升序排列
    }
};

// Dijkstra 算法
std::unordered_map<std::string, int> dijkstra(
    const std::unordered_map<std::string, std::vector<Edge>>& graph,
    const std::string& start) {
    std::unordered_map<std::string, int> distances;
    for (const auto& node : graph) {
        distances[node.first] = std::numeric_limits<int>::max(); // 初始化为无穷大
    }
    distances[start] = 0;

    std::priority_queue<std::pair<std::string, int>, std::vector<std::pair<std::string, int>>, Compare> pq;
    pq.push(std::make_pair(start, 0));

    while (!pq.empty()) {
        auto currentPair = pq.top();
        pq.pop();
        std::string current = currentPair.first;
        int currentDist = currentPair.second;

        if (currentDist > distances[current]) continue;

        for (const auto& edge : graph.at(current)) {
            int newDist = currentDist + edge.weight;
            if (newDist < distances[edge.to]) {
                distances[edge.to] = newDist;
                pq.push(std::make_pair(edge.to, newDist));
            }
        }
    }

    return distances;
}

int main() {
    // 输入图结构：一组三元组 (r1, r2, weight)
    std::vector<std::tuple<std::string, std::string, int>> edges = {
        std::make_tuple("A", "B", 4),
        std::make_tuple("A", "C", 2),
        std::make_tuple("B", "C", 5),
        std::make_tuple("B", "D", 10),
        std::make_tuple("C", "D", 3),
        std::make_tuple("D", "E", 4),
        std::make_tuple("C", "E", 8)
    };

    // 构建图的邻接表
    std::unordered_map<std::string, std::vector<Edge>> graph;
    for (const auto& edge : edges) {
        std::string from = std::get<0>(edge);
        std::string to = std::get<1>(edge);
        int weight = std::get<2>(edge);
        graph[from].push_back({ to, weight });
        graph[to].push_back({ from, weight }); // 如果是无向图
    }

    // 指定源点
    std::string start = "A";

    // 运行 Dijkstra 算法
    auto distances = dijkstra(graph, start);

    // 输出最短路径
    std::cout << "Shortest paths from " << start << ":\n";
    for (const auto& pair : distances) {
        std::string node = pair.first;
        int distance = pair.second;
        std::cout << "To " << node << ": " << (distance == std::numeric_limits<int>::max() ? "Unreachable" : std::to_string(distance)) << "\n";
    }

    return 0;
}
